Previous | 
Home
Section: Partnerships and Cooperations
International Initiatives
Inria Associate Teams: SAMBA
-
Title: “Synergies for Ameliorations and Mastering of Branch-and-Price Algorithms”
-
International Partner (Institution - Laboratory - Researcher):
-
The so-called Dantzig-Wolfe decomposition approach has not yet made its way into general purpose solvers for Mixed Integer Programming (MIP). Despite its proved efficiency, the use of the method is currently restricted to specific applications and requires ad-hoc algorithms developed by experts. Our project is to develop general purpose algorithms to make this method generic. We shall focus in particular on (i) preprocessing procedures, (ii) warm-starting, (iii) stabilization (to improve convergence), (iv) strategies for combining cut and column generation, and (v) primal heuristics. The project builds on the accumulated experience of both the Brazilian and the French teams that have done pioneering work in tackling complex applications and deriving generic solution strategies using this decomposition approach. The new algorithms are implemented and tested in the software platform BaPCod. Hence, the collaborative research on methodological developments should lead to, as a bi-product, a Version 2 of BaPCod as a state-of-the-art Branch-and-Price-and-Cut Solver. This prototype should (i) serve as proof-of-concept code for the research planned in thisproject and beyond, (ii) enable us to achieve new benchmark results on key problems,(iii) provide incentive for the use of the method by non experts, (iv) leverage technology transfer to industry.